Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai).
n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0).
Find two lines, which together with x-axis forms a container, such that the container contains the most water.

题目大意：给定一个大小为n的数组，这个数组代表点 (i,ai)，连接(i,ai)和(i,0)，形成了n条垂直于x轴的线段，每2条线段和x轴围成一个水桶，问哪一个水桶装的水最多。返回装水量

题目难度：Medium

/**
 * Created by gzdaijie on 16/5/11
 * 水桶短板效应, 装水量等于宽度*2个条线段较小值，
 * left = 0, right = length - 1，计算面积和短板, 短板在左边则右移,否则左移
 * 时间复杂度O(n)
 */
public class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length < 2) return 0;

        int left = 0;
        int right = height.length -  1;
        int shorter, result = 0;
        while (left < right) {
            shorter = Math.min(height[left], height[right]);
            result = Math.max(result, (right - left) * shorter);
            if (shorter == height[left]) {
                ++left;
            } else {
                --right;
            }
        }
        return result;
    }
}